package Hot100.Medium.GreedyAndDP.DynamicPlanning;

public class LC64_MinPathInGrid {
    public static void main(String[] args) {
        int[][] grid = {{1,3,1},{1,5,1},{4,2,1}};
        int[][] grid2 = {{1,2,3},{4,5,6}};
        LC64_MinPathInGrid solution = new LC64_MinPathInGrid();
        System.out.println(solution.minPathSum(grid2));
    }

    public int minPathSum(int[][] grid){
        int m = grid.length;
        int n = grid[0].length;
        // 确定dp数组含义：dp[i][j]表示走到ij位置时，最小的路径和
        int[][] dp = new int[m][n];
        // 初始化dp数组,显然只能初始化第一列以及第一行的位置，因为可以往下走以及往右走，其他位置都没法初始化
        dp[0][0] = grid[0][0];
        // 初始化第一行，只能从起点往右走。
        for(int i = 1; i < n; i++){
            dp[0][i] = dp[0][i - 1] + grid[0][i];
        }
        // 初始化第一列，只能从起点往下走
        for(int j = 1; j < m; j++){
            dp[j][0] = dp[j - 1][0] + grid[j][0];
        }
        // 确定递推公式，由于可以往右走以及往下走，因此在这两个路径中选择小的
        // dp[i][j] = min(dp[i][j - 1] + grid[i][j], dp[i - 1][j] + grid[i][j])
        // 确定递推顺序，显然是从前往后递推
        for(int i = 1; i < m; i++){
            for(int j = 1; j < n; j++){
                dp[i][j] = Math.min(dp[i][j - 1] + grid[i][j], dp[i - 1][j] + grid[i][j]);
            }
        }
        return dp[m - 1][n - 1];
    }
}
